package org.icop.frame.select;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Vector;

import org.icop.frame.eval.Evaluator;
import org.icop.model.MultiSet;
import org.icop.model.ValuedCorrespondence;
import org.jbpt.graph.abs.IEdge;
import org.jbpt.graph.abs.IGraph;
import org.jbpt.hypergraph.abs.IVertex;

public class LookAheadMappingSimSelector<G extends IGraph<E,V>, E extends IEdge<V>, V extends IVertex> extends AbstractSelector<G, E, V> implements Selector<G, E, V> {

	@Override
	public Set<ValuedCorrespondence<V>> select(G sg1, G sg2, Evaluator<G, E, V> evaluator, MultiSet<ValuedCorrespondence<V>> viableMappings) {

		assert(evaluator != null);
		
		//INIT
		Set<ValuedCorrespondence<V>> mapping  = new HashSet<ValuedCorrespondence<V>>();
		Set<ValuedCorrespondence<V>> openMappings = new HashSet<ValuedCorrespondence<V>>(viableMappings);
		double highestSimilarity = Double.MIN_VALUE;
		Random randomized = new Random();

		//STEP
		boolean doStep = true;
		while (doStep){
			doStep = false;
			Vector<ValuedCorrespondence<V>> bestCandidates = new Vector<ValuedCorrespondence<V>>();
			double newHighestSimilarity = highestSimilarity;

			for (ValuedCorrespondence<V> couple: openMappings){
				Set<ValuedCorrespondence<V>> newMapping = new HashSet<ValuedCorrespondence<V>>(mapping);
				newMapping.add(couple);
				double newSimilarity = evaluator.evaluate(sg1, sg2, newMapping); 

				if (newSimilarity > newHighestSimilarity){
					bestCandidates = new Vector<ValuedCorrespondence<V>>();
					bestCandidates.add(couple);
					newHighestSimilarity = newSimilarity;
				}else if (newSimilarity == newHighestSimilarity){
					bestCandidates.add(couple);
				}
			}
			
			/*
			 * Do 1 look ahead
			 */
			double maxSimilarityInNextStep = 0;
			Vector<ValuedCorrespondence<V>> newBestCandidates = new Vector<ValuedCorrespondence<V>>();
			if (bestCandidates.size() > 0){
				for (ValuedCorrespondence<V> candidate : bestCandidates) {
					Set<ValuedCorrespondence<V>> newOpenMappings = new HashSet<ValuedCorrespondence<V>>();
					for (ValuedCorrespondence<V> p: openMappings){
						if (!overlaps(p.getV1s(),candidate.getV1s()) && !overlaps(p.getV2s(),candidate.getV2s())){
							newOpenMappings.add(p);
						}
					}
					
					double maxSimilarityInNextStepForCandidate = Double.MIN_VALUE;
					
					for (ValuedCorrespondence<V> couple: openMappings){
						Set<ValuedCorrespondence<V>> newMapping = new HashSet<ValuedCorrespondence<V>>(mapping);
						newMapping.add(couple);
						double simForNextStepForCandidate = evaluator.evaluate(sg1, sg2, newMapping); 

						if (simForNextStepForCandidate > maxSimilarityInNextStepForCandidate){
							maxSimilarityInNextStepForCandidate = simForNextStepForCandidate;
						}
					}
					
					if (maxSimilarityInNextStepForCandidate == maxSimilarityInNextStep) {
						newBestCandidates.add(candidate);
					}
					else if (maxSimilarityInNextStepForCandidate > maxSimilarityInNextStep) {
						maxSimilarityInNextStep = maxSimilarityInNextStepForCandidate;
						newBestCandidates.clear();
						newBestCandidates.add(candidate);
					}
				}
			}

			
			if (newBestCandidates.size() > 0){
				//Choose a random candidate
				ValuedCorrespondence<V> couple = newBestCandidates.get(randomized.nextInt(newBestCandidates.size()));

				Set<ValuedCorrespondence<V>> newOpenMappings = new HashSet<ValuedCorrespondence<V>>();
				for (ValuedCorrespondence<V> p: openMappings){
					if (!overlaps(p.getV1s(),couple.getV1s()) && !overlaps(p.getV2s(),couple.getV2s())){
						newOpenMappings.add(p);
					}
				}
				openMappings = newOpenMappings;					

				mapping.add(couple);
				highestSimilarity = newHighestSimilarity;
				doStep = true;
			}			
		}

		//Return the smallest edit distance
		return mapping;
	}
	
}
